package Easy;

// 67.二进制求和
public class Solution67 {
    public static String addBinary(String a, String b) {
        int i = a.length() - 1, j = b.length() - 1;
        int jinwei = 0;
        char[] result = new char[a.length() > b.length() ? b.length() : a.length()];
        for (int k = result.length - 1; i > -1 && j > -1; i--, j--, k--) {
            int m = (int) (a.charAt(i)) - 48 + (int) (b.charAt(j)) - 48 + jinwei;
            if (m > 1) {
                jinwei = 1;
                if (m > 2) {
                    result[k] = '1';
                } else
                    result[k] = '0';
            } else if (m == 1) {
                jinwei = 0;
                result[k] = '1';
            } else {
                jinwei = 0;
                result[k] = '0';
            }
        }
        //如果a和b一样长，且最后有进位
        if (i == -1 && j == -1 && jinwei == 1) {
            return "1" + new String(result);
        }
        int def = a.length() > b.length() ? a.length() - b.length() : b.length() - a.length();
        //a和b一样长，且没有进位
        if (def == 0) {
            return new String(result);
        }
        char[] leftover = new char[def];
        //a和b不一样长，把剩余的加到前面
        for (; i > -1; i--) {
            int m = (int) (a.charAt(i)) - 48 + jinwei;
            if (m > 1) {
                jinwei = 1;
                if (m > 2) {
                    leftover[i] = '1';
                } else
                    leftover[i] = '0';
            } else if (m == 1) {
                jinwei = 0;
                leftover[i] = '1';
            } else {
                jinwei = 0;
                leftover[i] = '0';
            }
        }
        for (; j > -1; j--) {
            int m = (int) (b.charAt(j)) - 48 + jinwei;
            if (m > 1) {
                jinwei = 1;
                if (m > 2) {
                    leftover[j] = '1';
                } else
                    leftover[j] = '0';
            } else if (m == 1) {
                jinwei = 0;
                leftover[j] = '1';
            } else {
                jinwei = 0;
                leftover[j] = '0';
            }
        }
        //最后检查是否有进位
        if (jinwei == 0)
            return new String(leftover) + new String(result);
        return "1" + new String(leftover) + new String(result);
    }

    public static void main(String[] args) {
        System.out.println(addBinary("11", "1"));
    }
}
